/**
 * Created with Intellij IDEA.
 * Description:
 * User: wangj
 * Date: 2022-03-15
 * Time: 21:40
 */
class ListNode {
    public int val;//值
    public ListNode next;//后继信息
    public ListNode prev;//前驱信息

    public ListNode(int val) {
        this.val = val;
    }
}
public class LinkedList {

    public ListNode head;//标记双向链表的头节点

    public ListNode last;//标记双向链表的尾巴
    public int usedSize;

    //头插法
    public void addFirst(int data) {
        ListNode node=new ListNode(data);
        if(head==null){
            head=node;
            last=node;
        }
        else{
            node.next=head;
            head.prev=node;
            head=node;
        }
        this.usedSize++;
    }

    //尾插法
    public void addLast(int data) {
        ListNode node=new ListNode(data);
        if(last==null){
            head=node;
            last=node;
        }
        else{
            node.prev=last;
            last.next=node;
            last=node;
        }
        this.usedSize++;
    }

    //任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index, int data) {
        if(index<0||index>usedSize){
            throw new RuntimeException("index不合法！");
        }
        ListNode cur=head;
        ListNode node=new ListNode(data);
        while(index-1>0){
            cur=cur.next;
            index--;
        }
        if(cur==last){
            node.prev=cur;
            cur.next=node;
            last=node;
            this.usedSize++;
        }
        else if(cur==head){
            node.next=head;
            cur.prev=node;
            head=node;
            this.usedSize++;
        }else {
            ListNode curNext = cur.next;
            node.prev = cur;
            cur.next = node;
            node.next = curNext;
            curNext.prev = node;
            this.usedSize++;
        }
    }

    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key) {
        ListNode cur = this.head;
        while (cur != null) {
            if (cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }//删除第一次出现关键字为key的节点

    public void remove(int key) {
        ListNode cur = this.head;
        while (cur!=null){
            if(cur.val==key){
                if(head==last){
                    cur=head=last=null;
                    usedSize--;
                    return;
                }
                if(cur==head){
                    cur.next.prev=null;
                    head=cur.next;
                    cur=null;
                    usedSize--;
                    return;
                }
                if(cur==last){
                    cur.prev.next=null;
                    last=cur.prev;
                    cur=null;
                    usedSize--;

                    return;
                }else {
                cur.prev.next=cur.next;
                cur.next.prev=cur.prev;
                    usedSize--;

                    return;
                }
            }
            cur=cur.next;
        }
    }

    //删除所有值为key的节点
    public void removeAllKey(int key) {
        ListNode cur = this.head;
        while (cur!=null){
            if(cur.val==key){
                if(head==last){
                    cur=head=last=null;
                    usedSize--;
                    return;
                }
                if(cur==head){
                    cur.next.prev=null;
                    head=cur.next;
                    cur=null;
                    usedSize--;
                    cur=head;
                    continue;
                }
                if(cur==last){
                    cur.prev.next=null;
                    last=cur.prev;
                    cur=null;
                    usedSize--;
                    return;
                }else {
                    cur.prev.next=cur.next;
                    cur.next.prev=cur.prev;
                    usedSize--;
                    cur=cur.next;
                    continue;
                }
            }
            cur=cur.next;
        }
    }

    //得到单链表的长度
    public int size() {
        int count = 0;
        ListNode cur = this.head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

    public void display() {
        ListNode cur = this.head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    public void clear() {
        ListNode cur=head;
        ListNode curNext=cur.next;
        while (cur.next!=null){
            cur=null;
            cur=curNext;
            curNext=curNext.next;
        }
        last=null;
    }

}

